//Universidad del Valle de Guatemala
//Algoritmos y Estructuras de Datos
//Hoja de Trabajo #5
//David Ytzen Hsieh Lo #08225

import java.util.Comparator;
import java.util.Vector;

/**
 *
 * @author David Hsieh
 * @param <E>
 */
public class Heap<E> implements Comparator<Nodo>, InterfazColasP<E> {

    private Vector<Nodo<E>> heaps;
    private int cantidad, limite;
    

    /**
     *
     * @param limite
     */
    public Heap(int limite) {
        cantidad =0;
        this.limite = limite;
        heaps = new Vector(limite);
    }

    /**
     *
     * @param key
     * @param dato
     * @return
     */
    public boolean insertar(int key, E dato) {
        if(cantidad >= limite) 
            return false;
        Nodo nNodo = new Nodo(key, dato);
        heaps.add(cantidad, nNodo);
        subir(cantidad);
        cantidad++;
        return true;

    }

    /**
     *
     * @return
     */
    public E remover() {
        Nodo raiz = heaps.firstElement();
        cantidad--;
        heaps.set(0, heaps.get(cantidad));
        bajar(0);
        return (E) raiz.getDato();

    }
    

    /**
     *
     * @return
     */
    public boolean vacio() {
        if(cantidad > 0)
            return false;
        return true;
    }

    //Método para subir el nodo que se encuentra hasta abajo, esto sirva para cuando se
    //va a insertar un nuevo nodo y se necesita colocarlo en donde tiene que estar,
    //intercambiando posiciones durante su trayecto.
    /**
     *
     * @param index
     * 
     */
    public void subir(int index) {
        int padre = (index-1) /2;
        Nodo ultimo = heaps.get(index);

        while(index > 0 && compare(heaps.get(padre), ultimo) <0) {
            heaps.set(index, heaps.get(padre));
            index = padre;
            padre = (padre-1)/2;
            
        }
        
        heaps.set(index, ultimo);


    }

    //Método para bajar el nodo de hasta arriba, ya que al remover la raíz, ésta llega a ser
    //reemplazada por el último nodo, el cual debe ser recolocado donde tiene que estar,
    //intercambiando posiciones en su trayecto.
    /**
     *
     * @param index
     */
    public void bajar(int index) {
        int hijoMayor;
        Nodo top = heaps.get(index);
        while(index < cantidad/2) {
            int hijoIzq = 2 * index +1;
            int hijoDer = hijoIzq + 1;

            if(hijoDer < cantidad && compare(heaps.get(hijoIzq),heaps.get(hijoDer))<0)
                hijoMayor = hijoDer;
            else
                hijoMayor = hijoIzq;

            if(compare(top,heaps.get(hijoMayor))>=0)
                break;

            heaps.set(index, heaps.get(hijoMayor));
            index = hijoMayor;

        }

        heaps.set(index, top);
    }

    //Método para comparar las claves (keys) de los nodos.
    public int compare(Nodo o1, Nodo o2) {
        int clave1 = (o1.getClave());
        int clave2 = (o2.getClave());
           
        if(clave1 > clave2)
            return 1;
        else if(clave2 > clave1)
            return -1;

        return 0;

    }





}
